import java.util.Arrays;

/**
 * Created by L.jp
 * Description:给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
 * 如果无解，请返回-1.
 * User: 86189
 * Date: 2022-09-01
 * Time: 9:05
 */
public class Solution {
    public int minMoney (int[] arr, int aim) {
        if(aim==0){
            return 0;
        }
        //dp[i]表示组成i元需要的最少货币数,i从1到aim
        int[] dp=new int[aim+1];
        Arrays.fill(dp,aim+1);
        //初始化
        //0元金额兑换不到
        dp[0]=0;
        for(int i=1;i<=aim;i++){
            //每一种货币都要用到
            for(int j=0;j<arr.length;j++){
                //只有货币的面值小于等于目标数才可以兑换
                if(arr[j]<=i){
                    //取凑成指定金额所需货币数的最小值
                    //如果选取i作为一个指定金额，那么最小值就有可能是凑成i-arr[j]所需的货币数+1
                    dp[i]=Math.min(dp[i],dp[i-arr[j]]+1);
                }
            }
        }
        return dp[aim]>aim ? -1 : dp[aim];
    }
}
